package cn.cxq.learning.math;

import org.junit.jupiter.api.Test;

/**
 * 链接：https://www.nowcoder.com/questionTerminal/57d85990ba5b440ab888fc72b0751bf8?toCommentId=9150832
 * 来源：牛客网
 * <p>
 * [编程题]剪绳子
 * 热度指数：209619时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
 * 算法知识视频讲解
 * 给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],...,k[m]。请问k[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
 * <p>
 * 输入描述:
 * 输入一个数n，意义见题面。（2 <= n <= 60）
 * <p>
 * <p>
 * 输出描述:
 * 输出答案。
 * 示例1
 * 输入
 * 8
 * 输出
 * 18
 */
public class CutRope {

    @Test
    public void test() {
        System.out.println(cutRope(8));
    }

    // 使用动态规划解题：
    private int cutRope(int target) {

        if (target == 1) {
            return 1;
        }

        int[] dp = new int[target];

        dp[0] = 1;

        for (int i = 2; i <= target; i++) {

            int max = i;

            for (int j = 1; j < i; j++) {
                // 每次迭代取最大值，而动态规划思想的体现就在于：在分割之后取分割部分乘积的最大值（dp数组中找）。
                max = Math.max(max, dp[j - 1] * dp[i - j - 1]);
            }

            dp[i - 1] = max;
        }

        return dp[target - 1];
    }

    // 分割出越均匀的数，乘积会越大，所以我们不难想出从遍历所有情况需要指数级的时间复杂度跳跃到一个n的二次方时间复杂度的算法：
//    public int cutRope(int target) {
//
//        int result = 1;
//
//        for (int i = 1; i <= target; i++) {
//            int part = target / i; // 没部分的最小长度
//            int term = target % i; //需要加长一的次数
//            int plus = 1; //乘积中间值
//            for (int j = 0; j < i; j++) {
//                if (term-- > 0) {
//                    plus *= part + 1;
//                } else {
//                    plus *= part;
//                }
//            }
//            if (plus > result) {
//                result = plus;
//            } else {
//                break;
//            }
//        }
//
//        return result;
//    }
}
